/*
 * @lc app=leetcode.cn id=39 lang=cpp
 *
 * [39] 组合总和
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    vector<int> combine;            // 记录当前使用的数字
    vector<vector<int>> result;     // 记录最终的结果

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return result;
    }

    // 可以使用 index 之后的数据组成 target
    void dfs(vector<int>& candidates, int target, int index) {
        // 递归终止条件：可使用的下标大于数组范围
        if (index >= candidates.size()) return;
        // 递归终止条件：数字之和为 target
        if (target == 0) {
            result.push_back(combine);
            return;
        }

        // 取当前元素
        if (target >= candidates[index]) {
            combine.push_back(candidates[index]);
            dfs(candidates, target - candidates[index], index);
            combine.pop_back();
        }

        // 跳过当前元素
        dfs(candidates, target, index + 1);

        return;
    }
};
// @lc code=end

